package com.lun.easy;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class SumOfRootToLeafBinaryNumbers {
    public int sumRootToLeaf(TreeNode root) {
        int[] sum = {0};
    	sumRootToLeaf(root, 0, sum);
    	return sum[0];
    }
    
    private void sumRootToLeaf(TreeNode node, int pathSum, int[] sum) {
    	if(node == null)
    		return;
    	
    	pathSum = (pathSum << 1) | node.val;
    	
    	if(node.left == null && node.right == null)
    		sum[0] += pathSum;
    	
    	sumRootToLeaf(node.left, pathSum, sum);
    	sumRootToLeaf(node.right, pathSum, sum);
    }
    
    public int sumRootToLeaf2(TreeNode root) {
    	int sum = 0;
    	LinkedList<Object[]> stack = new LinkedList<>();
    	stack.push(new Object[] {root, 0});
    	
    	while(!stack.isEmpty()) {
    		Object[] arr = stack.pop();
    		TreeNode node = (TreeNode)arr[0];
    		int pathSum = (int)arr[1];
    		
    		pathSum = (pathSum << 1) | node.val;

    		if(node.left == null && node.right == null)
    			sum += pathSum;
    		
    		if(node.right != null)
    			stack.push(new Object[] {node.right, pathSum});

    		if(node.left != null)
    			stack.push(new Object[] {node.left, pathSum});
    	}
    	return sum;
    }
    
}
